/**
 * @Author: linzp
 * @Date: 2022/07/18/14:35
 */
public class demo0718 {
    public static void main(String[] args) {
//
//        ListNode head = new ListNode(1);
//        head.next = new ListNode(2);
//        head.next.next = new ListNode(3);
//        head.next.next.next = new ListNode(4);
//        System.out.println(swapPairs(head).val);

        int n = 8;
        while (n-- > 0) {
            System.out.println(n);
        }

    }

    static class ListNode {
        int val;
        ListNode next;

        public ListNode() {

        }

        public ListNode(int val) {
            this.val = val;
        }

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    /**
     * 206. 反转链表
     * 给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * <p>
     * 输入：head = [1,2,3,4,5]
     * 输出：[5,4,3,2,1]
     *
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {

        ListNode pre = null;
        ListNode cur = head;
        ListNode temp = null;
        while (cur != null) {
            temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;//cur=cur.next=null时退出
    }

    //递归
    public ListNode reverseList2(ListNode head) {
        return reverse(null, head);
    }

    private ListNode reverse(ListNode prev, ListNode cur) {
        if (cur == null) {//遍历到最后的节点了说明，就退出
            return prev;
        }
        ListNode temp = null;
        temp = cur.next;// 先保存下一个节点
        cur.next = prev;// 反转
        // 更新prev、cur位置
        // prev = cur;
        // cur = temp;
        return reverse(cur, temp);
    }

    /**
     * 24. 两两交换链表中的节点
     * 给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
     * <p>
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * <p>
     * 输入：head = [1,2,3,4]
     * 输出：[2,1,4,3]
     * 示例 2：
     * <p>
     * 输入：head = []
     * 输出：[]
     * 示例 3：
     * <p>
     * 输入：head = [1]
     * 输出：[1]
     *
     * @param head
     * @return 1234
     */
    public static ListNode swapPairs(ListNode head) {
        ListNode dummyNode = new ListNode(0);//虚拟头结点
        dummyNode.next = head;
        ListNode prev = dummyNode;
        /**
         *
         *  ListNode dummyNode = new ListNode(0);//虚拟头结点
         *         ListNode prev = new ListNode(0);
         *         dummyNode.next = head;
         *         prev.next = head;
         *        原以为这样是可以的，结果发现错了。 这里如果1234 就会输出134 因为dummyNode.next一直是1没改变过
         *         原因是上面的 ListNode prev = dummyNode;是引用传递。这样第一次改变pre.next时
         *         dummyNode.next也是跟着改变的，也就是交换后的dummyNode.next还是等于新的head直到 prev = head;时pre就跟dummyNode没关系了
         */
        while (prev.next != null && prev.next.next != null) {
            ListNode temp = head.next.next;
            prev.next = head.next;
            head.next.next = head;
            head.next = temp;//上面3步是按顺序改变next
            prev = head;
            head = head.next;
        }
        return dummyNode.next;

    }

    //递归版本
    public ListNode swapPairs2(ListNode head) {
        // base case 退出提交
        if(head == null || head.next == null) return head;
        // 获取当前节点的下一个节点
        ListNode next = head.next;
        // 进行递归
        ListNode newNode = swapPairs2(next.next);
        // 这里进行交换
        next.next = head;
        head.next = newNode;

        return next;
    }

    /**
     * 19. 删除链表的倒数第 N 个结点
     * 给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
     * <p>
     * <p>
     * <p>
     * 示例 1：
     * <p>
     * <p>
     * 输入：head = [1,2,3,4,5], n = 2
     * 输出：[1,2,3,5]
     * 示例 2：
     * <p>
     * 输入：head = [1], n = 1
     * 输出：[]
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {

        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode fastNode = dummyNode;
        ListNode slowNode = dummyNode;
        while (n-- > 0) {//先-后比较 共n次
            fastNode = fastNode.next;
        }
        ListNode pre = null;//记录slow的前一个节点，删除时有用
        while (fastNode != null) {
            pre = slowNode;
            fastNode = fastNode.next;
            slowNode = slowNode.next;
        }
        //删除节点
        pre.next = slowNode.next;
        slowNode.next = null;

        return dummyNode.next;
    }
}
